package shenrudigui;

import java.util.HashSet;
import java.util.Set;

public class _04合法括号 {
    /**
     * 1.输出合法的括号组合
     * 输入括号对数
     * 输出所有合法组合
     * 输入:3
     * 输出:()()(),((())),(()()),()(()),(())(),
     * 2.判断一个字符串是否合法
     */
    public static void main(String[] args) {
        Set<String> set = parenthesis(3);
        for (String s : set) {
            System.out.println(s);
        }
        System.out.println(set.size());
    }

    public static Set<String> parenthesis(int n) {
        Set<String> s_n = new HashSet<>();
        if (n == 1) {
            s_n.add("()");
            return s_n;
        }
        Set<String> s_n_1 = parenthesis(n - 1);
        for (String eOfN_1 : s_n_1) {
            s_n.add("()" + eOfN_1); //左边加括号
            s_n.add(eOfN_1 + "()"); //右边加括号
            s_n.add("(" + eOfN_1 + ")");//外层加括号
            //内部加括号
            for (int i = 0; i < eOfN_1.length(); i++) {
                char c = eOfN_1.charAt(i);
                if (c == '('){
                    //只要这个字符是左括号，我们就可以在其后插入一对括号
                    s_n.add(eOfN_1.substring(0, i + 1) + "()" + eOfN_1.substring(i + 1));
                }
            }
        }
        return s_n;
    }
}
